/*
 * @FilePath: /data-and-structure-lv/06/heap-sort/heap-sort.c
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-12-18 12:58:42
 * @Author: zsk
 * @Copyright: open source
 * @LastEditors: zsk
 * @LastEditTime: 2022-01-01 13:34:55
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define LEFT(i) (2 * i)
#define RIGHT(i) (2 * i + 1)
#define PARENT(i) (i / 2)

#define BASE_POINT 2
#define TOTAL_HEIGHT 3
#define ADJUST_FACTOR 3
#define REFERENCE_DISTANCE 90

typedef int ElementType;
typedef struct PointHight_Tag
{
    int point;
    int offset;
    struct PointHight_Tag *next;
} PointHight;
typedef struct PointHightList_Tag
{
    int treeHeight;
    int height;
    PointHight *pointHight;
    struct PointHightList_Tag *next;
} PointHightList;

void max_heapify(ElementType *a, int i, int heap_size)
{
    int l = LEFT(i);
    int r = RIGHT(i);
    int largest = -1;

    if (l <= heap_size && a[l] < a[r])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if (r <= heap_size && a[r] > a[largest])
    {
        largest = r;
    }
    if (largest != i)
    {
        ElementType temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        max_heapify(a, largest, heap_size);
    }
}
void record_child(int root, PointHightList *head, PointHightList *prev, int size, int height, int reference_distance)
{
    int left = LEFT(root) <= size ? LEFT(root) - 1 : -1;
    int right = RIGHT(root) <= size ? RIGHT(root) - 1 : -1;
    if (left == -1 && right == -1)
    {
        /* code */
        return;
    }

    PointHightList *headtemp = head;
    PointHightList *curlist;
    for (int i = 0; i < height; i++)
    {
        if (!headtemp->next && i == (height - 1))
        {
            /* code */
            curlist = malloc(sizeof(PointHightList));
            curlist->height = height;
            head->treeHeight = fmax(height, head->height);
            headtemp->next = curlist;
            break;
        }
        headtemp = headtemp->next;
    }
    if (!curlist)
    {
        curlist = headtemp;
    }

    if (left != -1)
    {
        PointHight *pointHightLeft = malloc(sizeof(PointHight));
        pointHightLeft->point = left;
        pointHightLeft->offset = reference_distance - (TOTAL_HEIGHT - height) * BASE_POINT * ADJUST_FACTOR - 2 * BASE_POINT;
        pointHightLeft->next = NULL;
        PointHight *temp = curlist->pointHight;
        if (temp != NULL)
        {
            for (; temp->next != NULL;)
            {
                temp = temp->next;
            }
            temp->next = pointHightLeft;
        }
        else
        {
            curlist->pointHight = pointHightLeft;
        }

        record_child(left + 1, head, curlist, size, height + 1, pointHightLeft->offset);
    }

    if (right != -1)
    {

        PointHight *pointHightRight = malloc(sizeof(PointHight));
        pointHightRight->point = right;
        pointHightRight->offset = reference_distance + (TOTAL_HEIGHT - height) * BASE_POINT * ADJUST_FACTOR + 2 * BASE_POINT;
        pointHightRight->next = NULL;
        PointHight *temp = curlist->pointHight;
        if (temp != NULL)
        {
            for (; temp->next != NULL;)
            {
                temp = temp->next;
            }
            temp->next = pointHightRight;
        }
        else
        {
            curlist->pointHight = pointHightRight;
        }
        record_child(right + 1, head, curlist, size, height + 1, pointHightRight->offset);
    }
}

void print_array_to_tree(ElementType *a, int root, int size)
{
    int height = 0;
    PointHightList *list = malloc(sizeof(PointHightList));
    list->height = height;
    list->treeHeight = height;

    PointHight *pointHight = malloc(sizeof(PointHight));
    pointHight->point = root - 1;
    pointHight->offset = REFERENCE_DISTANCE;
    pointHight->next = NULL;
    list->pointHight = pointHight;

    list->next = NULL;
    record_child(root, list, list, size, height + 1, REFERENCE_DISTANCE);

    int lastOffset = 0;
    PointHightList *listTemp = list;
    while (listTemp != NULL)
    {
        PointHight *curPoint = listTemp->pointHight;
        int k = 1;
        while (curPoint != NULL)
        {

            lastOffset = curPoint->offset - lastOffset;
            for (int i = 0; i < lastOffset; i++)
            {
                printf(" ");
            }
            printf("%2d", a[curPoint->point]);
            lastOffset=curPoint->offset+BASE_POINT;
            curPoint = curPoint->next;
            k++;
        }
        lastOffset = 0;
        listTemp=listTemp->next;
        printf("\n");
    }
}

void main()
{
    // ElementType a[] = {27, 17, 30, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0};
    // int size = 14;
    // print_array_to_tree(a, 1, size);

    ElementType b[15];
    for(int i=0;i<15;i++){
        b[i]=i;
    }
    print_array_to_tree(b,1,15);
}